package com.lzp.leetcode.dp.simple;

/**
 * 最大子数组乘积
 *
 * @author lzp
 * @date 2020/7/6
 */
public class D5_LC152_MaxProduct {
    /**
     * 此题问题所在，如果nums[i]为正数，我们希望以nums[i - 1]结尾的连续子序列乘积最大；为负数，则希望最小。
     *
     * 复杂度 n
     *
     * @param nums
     * @return
     */
    public int maxProduct(int[] nums) {
        int n = nums.length;

        // 最大和最小子序列数组
        int[] f = new int[n];
        int[] g = new int[n];

        // 初始化
        f[0] = nums[0];
        g[0] = nums[0];
        int res = nums[0];
        for (int i = 1; i < n; ++i) {
            // f[i] = 以nums[i]结尾的连续子序列的最大乘积
            // g[i] = 以nums[i]结尾的连续子序列的最小乘积
            // 但并不意味着有nums[i]才是最大
            f[i] = Math.max(nums[i], Math.max(nums[i] * f[i - 1], nums[i] * g[i - 1]));
            g[i] = Math.min(nums[i], Math.min(nums[i] * f[i - 1], nums[i] * g[i - 1]));
            res = Math.max(res, f[i]);
        }
        return res;
    }
}
